The Number of Symmetrical Choices

Memory limit: 32 MB

We are given two sequences of words: and , with . For every , , we chose one of the two words: or . The chosen words are merged in order of increasing indices. The choice consists of steps. In each step we decide to take the -th word from the first or from the second sequence of words. More formally: the choice is a sequence of length whose elements are numbers and . It is possible that different choices lead to the same word. We say that a choice is symmetrical if its result is a palindrome, i.e. a word that is identical when we read it from left to right and from right to left.

Task

Write a program that:

• reads from the standard input: the number and two sequences of words and ,
• computes the number of symmetrical choices for the given sequences,
• writes the result to the standard output.

Input

In the first line of the standard input there is one positive integer . In the following lines there are written consecutive words of the sequence — one word in one line. In the following lines there are written (in the similar way) consecutive words of the sequence . Each word consists solely of small letters of the English alphabet (from a to z). The total length of all words is from the range .

Output

In the standard output there should be written one non-negative integer — the number of symmetrical choices.

Example

For the input data:

5
ab
a
a
ab
a
a
baaaa
a
a
ba

the correct result is:

12

Task author: Wojciech Rytter.